package com.twogroup;

public class CodeDay02 {

    public static void main(String[] args) {
	// write your code here
        System.out.println("java\n语言");

        //输出0--100间能同时被3和5 整除的整数；DIY
        System.out.println("========输出0--100间能同时被3和5 整除的整数；DIY========");
        for (int i = 0; i <= 100; i++) {
            if(i%3 == 0 && i%5 == 0) {
                System.out.println(i);
            }
        }
        System.out.println("========二分查找 循环=========");
        // 二分查找 循环
        int i = search1(new int[]{2, 4, 6, 8, 10}, 4);
        System.out.println("查找的元素4在下标为"+i+"上");

        System.out.println("========二分查找 递归=========");
        // 二分查找 递归
        i = search2(new int[]{2, 4, 6, 8, 10}, 4);
        System.out.println("查找的元素4在下标为"+i+"上");

        // 测试双向链表
        System.out.println("========测试双向链表=========");
        CustomLinkedList<Integer> customLinkedList = new CustomLinkedList();

        // 尾插法
        customLinkedList.addLast(1);
        customLinkedList.addLast(2);
        customLinkedList.addLast(3);
        // 头插法
        customLinkedList.addFirst(4);
        customLinkedList.addFirst(5);
        // 下标插法
        customLinkedList.addIndex(1,11);
        customLinkedList.addIndex(1,22);
        customLinkedList.addIndex(1,11);
        // 展示
        customLinkedList.display();
        // 删除指定的全部data
        customLinkedList.removeAll(11);
        customLinkedList.display();
        // 判断是否包含
        System.out.println(customLinkedList.contains(1));
        System.out.println(customLinkedList.contains(11));
        System.out.println(customLinkedList.contains(6));
        // 长度
        System.out.println(customLinkedList.size());

    }
    // 二分查找 循环
    public static int search1(int[] nums, int target) {
        //二分查找可以利用循环迭代和递归两种方式来实现，这里先介绍第一种循环遍历的方式
        int len=nums.length;
        int start=0;
        int end=nums.length-1;
        // 判断开始下标小于结束下标
        while (start<=end){
            // 先计算中间值，计算中间值，为了更快的效率，使用位移操作，等同于(left + right) / 2
            int mid=(start+end)>>1;
            // 中间值大于要找的值，取前1/2，结束下标为中间值减一
            if (nums[mid]>target){
                end=mid-1;
            // 中间值小于要找的值，取后1/2，开始下标为中间值加一
            }else if (nums[mid]<target){
                start=mid+1;
            // 中间值即为要找的值，返回要找的下标
            }else {
                return mid;
            }
        }
        // 没找到返回-1
        return -1;
    }
    // 二分查找 递归 与循环类似，额外需要将返回的条件传递到函数参数上
    public static int search2(int[] nums, int target) {
        // 递归函数需要传递 排序好的数组，起始与结束位置下标，要查询的数
        return binSearch(nums,0,nums.length-1,target);
    }
    private static int binSearch(int[] nums,int low,int high,int target){
        if (low>high){
            return -1;
        }
        int mid=(high+low)>>2;
        if (nums[mid]>target){
            return binSearch(nums, low, mid-1,target);
        }else if (nums[mid]<target){
            return binSearch(nums,mid+1,high,target);
        }else {
            return mid;
        }
    }
}